
// https://leetcode.cn/problems/longest-increasing-subsequence/submissions/498301113/

function lengthOfLIS(nums: number[]): number {
    const n = nums.length;
    // 定义状态方程,里面存储的当前位置最长子序列的最大值
    const dp:number [] = new Array(n).fill(1);

    let max = dp[0]
    for(let i = 1; i < n; i++) {
        for(let j = 0; j < i; j++) {
            // 找到之前遍历过的数字中比当前位置小的数字
            if (nums[j] < nums[i]){
                // 因为这里的dp[i]是在for循环里面，所以里面的dp[i] 是要多次赋值的，
                //所以要拿之前赋过值的dp[i] 和之前比自己小的位置的大的值加1进行比较，选出较大的值再赋值给dp[i]
                dp[i] =  Math.max(dp[i],dp[j] + 1);
                max = Math.max(max,dp[i]);
            }
        }
    }
    return max;
};

export {}